/**
* @description: 720. 词典中最长的单词
* @author hewei
* @date 2022/8/17 14:25
* @version 1.0
*/

public class LongestWord {

    public static void main(String[] args) {
        LongestWord longestWord = new LongestWord();
        String[] nums = {"ogz","eyj","e","ey","hmn","v","hm","ogznkb","ogzn","hmnm","eyjuo","vuq","ogznk","og","eyjuoi","d"};
        System.out.println(longestWord.longestWord(nums));
    }

    public String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.add(word);
        }
        trie.search(trie);
        return trie.ans;
    }

    class Trie {
        Trie[] next;
        int end;
        String ans;
        StringBuilder stringBuilder;

        public Trie() {
            next = new Trie[26];
            end = 0;
            ans = "";
            stringBuilder = new StringBuilder();
        }

        public void add(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = new Trie();
                node = node.next[c - 'a'];
            }
            node.end++;
        }

        public void search(Trie node) {
            int count = 0;
            for (int i = 0; i < 26; i++) {
                if (node.next[i] != null && node.next[i].end != 0) {
                    stringBuilder.append((char) (i + 'a'));
                    search(node.next[i]);
                    stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                } else ++count;
            }
            if (count == 26 && (stringBuilder.length() > ans.length()
                    || (stringBuilder.length() == ans.length() && stringBuilder.toString().compareTo(ans) < 0)))
                ans = stringBuilder.toString();
        }
    }
}
